package LinkTest;
import java.util.ArrayList;
//合并k个已经排序的链表
public class LinkkSum {
    static class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
 }
    public ListNode sun(ListNode head1,ListNode head2){
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        ListNode head=new ListNode(0);
        ListNode cur=head;
        while(head1!=null&&head2!=null){
            if(head1.val<=head2.val){
                cur.next=head1;
                head1=head1.next;
            }else{
                cur.next=head2;
                head2=head2.next;
            }
            cur=cur.next;
        }
        if(head1!=null){
            cur.next=head1;
        }else{
            cur.next=head2;
        }
        return head.next;
    }
    public ListNode divre(ArrayList<ListNode> lists,int left,int right){
        if(left>right){
            return null;
        }
        else if(left==right){
            return lists.get(left);
        }
        int mid=(left+right)/2;
        return sun(divre(lists,left,mid),divre(lists,mid+1,right));
    }
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        return divre(lists,0,lists.size()-1);
    }
}
